package 回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 括号生成22.java
 * @createTime 2022年11月08日 19:55:00
 */
public class 括号生成22 {
	List<String> result = new ArrayList<>();

	public List<String> generateParenthesis(int n) {
		StringBuilder sb = new StringBuilder();
		backTrace(n, n,sb);
		return result;
	}



	/**
	 * @param leftNum  左括号的个数
	 * @param rightNum 右括号的数量
	 */
	public void backTrace(int leftNum, int rightNum,StringBuilder sb) {
		/**
		 * 终止条件，校验合法性
		 * 1. 左边括号的数量大于右括号的数量则不合法
		 * 2. 左括号和右括号数量任意一个小于0也不行
		 * 3. 只有左右括号都为0，才说明复合
		 */
		if (leftNum > rightNum) {
			return;
		}
		if (leftNum < 0 || rightNum < 0) {
			return;
		}
		if (leftNum == 0 && rightNum == 0) {
			result.add(sb.toString());
		}

		//做选择,放左括号
		backTrace(leftNum-1,rightNum,sb.append("("));
		//撤销选择
		sb.deleteCharAt(sb.length()-1);

		//做选择，放右括号
		backTrace(leftNum,rightNum-1,sb.append(")"));
		sb.deleteCharAt(sb.length()-1);
	}
}
